package 算法练习;/**
 * @author： li
 * @date： 2022-01-12 15:42
 * @version 1.0
 */
/*问题描述
　　逗志芃励志要成为强力党，所以他将身上所以的技能点都洗掉了重新学技能。现在我们可以了解到，每个技能都有一个前提技能，
    只有学完了前提技能才能学习当前的技能（有一个最根本的技能不需要前提技能）。学习每个技能要消耗一个技能点，
    然后可以获得这个技能的威力值。由于逗志芃要陪妹子，所以他希望你教他如何点技能使得威力值最大从而成为强力党。
输入格式
　　第一行两个数n，m表示有n个技能和m个技能点。第二行有n个数，第i个数表示第i个技能的威力值。
　　之后的n-1行，每行两个数x,y，表示y技能的前提技能是x，也就是说先学第x个技能才能学弟y个技能。
输出格式
　　一个数，最大的威力值。
样例输入
3 2
1 10 20
1 2
1 3
样例输出
21
数据规模和约定
　　0<n,m<=200, 技能的威力值不超过200。
 */
import java.util.ArrayList;
import java.util.Scanner;
public class 强力党逗志芃_un {
    static int n;//技能数
    static int m;//技能点
    static int[] wl;//存技能威力
    static int[][] jnwl;//存技能的威力的状态
    static int[][] qt;//存技能前提
    static int ans=0;
//    static int ans1=0;
    static int max1=0;//最大值
    static int max2=0;//次大值
    static int max11=0;//最大值
    static int max22=0;//次大值
    static int max=0;//最大值
    static int[][] wpz;
    static int[][] max_wpz;
    static int[][] maxjnwl;
    static int[][] maxjnwl2;
    static int[][] maxjnwl11;
    static int[][] maxjnwl22;
    static int count1=0;
    static int zzmax;
    static int 求状态的值(int k,int[] wl1){
            for(int j=1;j<=n;j++){
                if(wpz[k][1]==0) return Math.max(ans,max1+max2);
                if(wpz[k][j]!=0){
                    ans=Math.max(求状态的值(wpz[k][j],wl1),ans);
                    if(max1+wl1[wpz[k][j]]>max1) {
                        max2=max1;
                        max1=wl1[wpz[k][j]];
                    }else if(max1+wl[wpz[k][j]]>max2) {
                        max2=wl1[wpz[k][j]];
                    }
                }
                if(wpz[k][j]==0) return Math.max(max1+max2,ans);
//                System.out.println("max1:"+max1);
//                System.out.println("max2:"+max2);
//                System.out.println("max1+max2:"+(max1+max2));
//                System.out.println("ans:"+ans);
                maxjnwl[k][j]=max1;
                maxjnwl2[k][j]=max2;
            }
        return Math.max(ans,max1+max2);
    }
    static int 求最大的值(int k,int ans1){
            for(int j=1;j<=n;j++){
                if(wpz[k][1]==0) return ans1;
                if(count1<m-1){
                    if(wpz[k][j]!=0){
                        count1++;
                        ans1=Math.max(求最大的值(wpz[k][j],ans1),ans1);

                    }
                }
                if(count1==m-1){
                    count1=1;
                    max11=max;
                    max=Math.max(求最大的值(wpz[k][j+1],ans1),ans1);
                    max=0;
                }
                if(wpz[k][j]==0) return ans1;
            }
        return ans1;
    }


    public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    n=sc.nextInt();
    m=sc.nextInt();
    jnwl=new int[n+1][n+1];
    qt=new int[n+1][m+1];
    wl=new int[n+1];
    wpz=new int[n+1][n+1];
    max_wpz=new int[n+1][n+1];
    maxjnwl=new int[n+1][n+1];
    maxjnwl2=new int[n+1][n+1];
    maxjnwl11=new int[n+1][n+1];
    maxjnwl22=new int[n+1][n+1];
    for(int i=1;i<=n;i++){
        wl[i]=sc.nextInt();
    }
    for(int i=1;i<n;i++){
        for(int j=1;j<=2;j++)
            qt[i][j]=sc.nextInt();
    }
    for(int i=1;i<=n;i++){
            jnwl[qt[i][1]][qt[i][2]]=wl[qt[i][2]];
    }
    for(int i=1;i<=n;i++){
        jnwl[0][i]=i;
    }
    for(int i=1;i<=n;i++){
        jnwl[i][0]=i;}
        int k=1;
    for(int i=1;i<=n;i++) {
//        System.out.print(jnwl[i][0]+" ");
        for (int j = 1; j <= n; j++){
            if(jnwl[i][j]!=0){
                  wpz[i][k]=jnwl[0][j];
                    k++;
            }
            if(j==n) k=1;
//                System.out.print(jnwl[0][j]+":"+jnwl[i][j]+" ");
//            if(j==n)
//                System.out.println(" ");
        }
    }
//    int count=0;
//    for(int i=1;i<=n;i++){
//        for(int j=1;j<=n;j++){
//            if(wpz[i][j]!=0){
//                max_wl=Math.max(max_wl,wl[wpz[i][j]]);
//                count++;
//            }
//        }
//        max_wpz[i][0]=max_wl;
//        max_wpz[i][1]=count;
//        count=0;
//        max_wl=0;
//    }
        for(int i=0;i<=n;i++) {
            for (int j =0; j <= n; j++){
                System.out.print(wpz[i][j]+" ");
                if(j==n)
                System.out.println(" ");
            }
        }
//        System.out.println(max_wl);
        求状态的值(1,wl);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                System.out.print(maxjnwl[i][j]+" ");
            }
            System.out.println(" ");
        }
    zzmax=求最大的值(1,0);
        System.out.println(zzmax);
    }
}
